1124. 表现良好的最长时间段

Similar Question

Solution Tips

方案一: 前缀和变体

525. 连续数组 要求的是和为 0 的, 这一题要求的是和大于 0 的.

var longestWPI = function (hours) {
    // 大于 8 小时的视为 1
    // 小于 8 小时的视为 -1
    // 计算前缀和, 只要前缀和大于 0, 就可以去统计前面的有多少 减去之后依然大于 0 的, 就是长度
    // 假如当前前缀和为 -5, 那么前面的 map[-5] 以上的都可以减去, 减去以后和就是正数了, 剩下的就是符合题意的长度
    // 要找的是和大于 0 的子数组
    // 前缀和大于0的话, 前缀长度就是最长的
    // 前缀和小于0的话, 就通过哈希map找有没有 target 减完之后能大于 0 的
    const map = {};
    let res = 0;
    let prefixSum = 0;
    for (let i = 0; i < hours.length; i++) {
        const item = hours[i] > 8 ? 1 : -1;
        prefixSum += item;
        if (map[prefixSum] === undefined) {
            // 不需要数组, 最早出现的距离最远, 贪心, 更符合题意
            map[prefixSum] = i;
        }
        // else {
        //     map[prefixSum] = [i];
        // }

        if (prefixSum > 0) {
            // 直接比较长度
            res = Math.max(res, i + 1);
        }
        else {
            // 找找前面的哈希表中, 有没有出现过最远的
            // 找 keys 中小于 prefixSum 的, 减去之后的子数组就是大于 0 的了
            // 比如 prefixSum 当前为 -5, 找到一个 -6 的前缀和, 减去之后剩余 1
            // 每次都需要遍历一次 map, 需要优化, 让 map keys 有序
            for (const [sum, index] of Object.entries(map).sort(([key1], [key2]) => key1 - key2)) {
                if (sum < prefixSum) {
                    res = Math.max(i - index, res);
                }
                else {
                    break;
                }
            }
        }
    }

    return res;
};

因为前缀和是从 0 开始的, 一个小于 - 1 的前缀和, 索引一定是位于 -1 之后的, 这样才能不断累积负数大于 -1. 基于这一点, 其实只需要找到 prefixSum[i] - 1 的 target 即可, 就完全转换为熟悉的题目了

var longestWPI = function(hours) {
    const n = hours.length;
    const map = new Map();
    let s = 0, res = 0;
    for (let i = 0; i < n; i++) {
        s += hours[i] > 8 ? 1 : -1;
        if (s > 0) {
            res = Math.max(res, i + 1);
        } else {
            if (map.has(s - 1)) {
                res = Math.max(res, i - map.get(s - 1));
            }
        }
        if (!map.has(s)) {
            map.set(s, i);
        }
    }
    return res;
};

方案二: 单调栈